use std::{collections::HashMap, hash::Hash};

struct TopVotedCandidate {
  winner: Vec<usize>,
  time: Vec<i32>
}

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * let obj = TopVotedCandidate::new(persons, times);
 * let ret_1: i32 = obj.q(t);
 */


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl TopVotedCandidate {

    fn new(persons: Vec<i32>, times: Vec<i32>) -> Self {
      let mut voter = TopVotedCandidate {
        winner: vec![],
        time: times.clone(),
      };
      let mut count = 0;
      if let Some(max) = persons.iter().reduce(|a, b| if a > b { a } else { b }) {
        count = *max as usize;
      }
      let mut last_voted_time = vec![-1; count + 1];
      let mut vote_count = vec![0; count + 1];
      let mut curr_winner = 0;
      let mut curr_count = 0;
      persons.iter().zip(times.iter()).for_each(|(target, time)| {
        let index = *target as usize;
        vote_count[index] += 1;
        last_voted_time[index] = *time;
        if vote_count[index] >= curr_count {
          curr_winner = index;
          curr_count = vote_count[index];
        }
        voter.winner.push(curr_winner);
      });
      voter
    } 
    
    fn q(&self, t: i32) -> i32 {
      return self.winner[bi_search(&(self.time), t)] as i32;
    }
}

fn bi_search(nums: &Vec<i32>, target: i32) -> usize {
  let mut l: usize = 0;
  let mut r = nums.len();
  let mut m: usize = (l + r) / 2;
  while l<m {
      if nums[m] == target {
          return m;
      }
      match nums[m] - target > 0 {
          true => {
              r = m;
              
          }
          false => {
              l = m;
          }
      }
      m = (l + r) / 2;
  }
  return m;
}

